package com.lqian.set;

import java.util.HashSet;

/**
 * @Author Melody_LQ
 * @Date 2021/8/12 16:28
 * @Description
 * 1.HashSet底层是HashMap
 * 2.添加一个元素时，先得到hash值 --> 会转成索引值
 * 3.找到存储数据表table 看这个索引位置是否已经存放了元素
 * 4.如果没有 就直接加入
 * 5.如果有，调用equals比较，如果相同，就放弃添加，如果不相同，则添加到该链表的最后
 * 6. 在JDK1.8中，如果一条链表的元素个数到达（默认是8），并且table的大小>= (默认64) 就会进行树化（红黑树）
 *
 * @Since version-1.0
 */
public class _HashSetSource {
    public static void main(String[] args) {


        HashSet hashSet = new HashSet();
        hashSet.add("a");
        hashSet.add("b");
        hashSet.add("a");
        System.out.println("hashSet -->"+hashSet);

        /**
         * 1.先执行构造器 HashSet()
         *  public HashSet() {
         *         map = new HashMap<>();
         *     }
         *
         * 2. 执行add()
         *  public boolean add(E e) { //e  = "a"
         *         return map.put(e, PRESENT)==null;
         *     }
         *
         * 3. 再执行put() 会通过hash(key) 得到key对应的hash值 算法:(h = key.hashCode()) ^ (h >>> 16)
         * //key = e;  V value= PRESENT --> private static final Object PRESENT = new Object(); PRESENT不变 共享(static)，占位 hashMap
         *  public V put(K key, V value) {
         *         return putVal(hash(key), key, value, false, true);
         *     }
         *
         * 4. 执行 putVal方法
         *  final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
         *                    boolean evict) {
         *         Node<K,V>[] tab; Node<K,V> p; int n, i; // 定义了辅助变量
         *         //table 就是hashMap的一个数组，类型是Node[]
         *         //if 语句表示如果当前table 是null 或者大小=0
         *         if ((tab = table) == null || (n = tab.length) == 0)
         *         //就是第一次扩容，到16个空间
         *             n = (tab = resize()).length;
         *         // (1)根据key 得到hash 去计算改key应该存放到table表中的哪个索引位置
         *         //并把这个位置的对象，赋值给p
         *         // (2)判断p 是否为null
         *         //   (2.1) 如果p为null 表示还没存放元素，就会创建一个Node(key = "a",value="PRESENT")
         *         //   (2.2) 就放在该位置 tab[i] = newNode(hash, key, value, null);
         *         if ((p = tab[i = (n - 1) & hash]) == null)
         *             tab[i] = newNode(hash, key, value, null);
         *         else {
         *             Node<K,V> e; K k;//辅助变量
         *             //如果当前索引位置对应的链表的第一个元素和准备添加的key(key 是一个对象)的hash值一样
         *             //并且满足 下面两个条件之一：
         *             // (1) 准备加入的key 和p指向的Node节点的key是同一个对象、
         *             // (2) p指向的Node节点的key的 equals() 和 准备加入对象的key比较后相同
         *             // 就不能加入
         *             if (p.hash == hash &&  // 添加 "a" 和 "b"   False
         *                 ((k = p.key) == key || (key != null && key.equals(k))))
         *                 e = p;
         *              //再判断 p 是不是一颗红黑树
         *              // 如果是一颗红黑树 就调用putTreeVal() 来进行添加
         *             else if (p instanceof TreeNode)
         *                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
         *             else {//如果table对应索引位置，已经是一个链表了，就使用for 循环比较机制
         *                  //(1) 依次和该链表的每一个元素比较后。都不相同，则加入到该链表的最后 break退出死循环
         *                      注意：在把元素添加到链表后，立即判断 该链表是否已经到达了8个节点
         *                       // TREEIFY_THRESHOLD = 8
         *                           if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
         *                            treeifyBin(tab, hash);
         *                      就调用treeifyBin() 对当前这个链表进行树化(转成红黑树)
         *                      注意：在进行树化(转成红黑树)之前，要判断
         *                      if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
         *                            resize();
         *                      //如果上面条件成立 则先table扩容
         *                      // 只有上面条件不成立时，才转成红黑树
         *                  //(2) 依次和该链表的每一个元素比较过程中，如果有相同的情况，就直接break
         *                 for (int binCount = 0; ; ++binCount) {
         *                     if ((e = p.next) == null) {
         *                         p.next = newNode(hash, key, value, null);
         *                         // TREEIFY_THRESHOLD = 8
         *                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
         *                             treeifyBin(tab, hash);
         *                         break;
         *                     }
         *                     if (e.hash == hash &&
         *                         ((k = e.key) == key || (key != null && key.equals(k))))
         *                         break;
         *                     p = e;  // p e 的指向关系
         *                     //e是node节点 (e = p.next) == null) 判断p.next 会不会等于null 不等于 e.hash  往下一个节点移动
         *
         *                 }
         *             }
         *             if (e != null) { // existing mapping for key
         *                 V oldValue = e.value;
         *                 if (!onlyIfAbsent || oldValue == null)
         *                     e.value = value;
         *                 afterNodeAccess(e);
         *                 return oldValue;
         *             }
         *         }
         *         ++modCount;
         *         if (++size > threshold)
         *             resize();
         *         afterNodeInsertion(evict);
         *         return null;  // return null代表成功
         *     }
         */
    }
}
